import java.util.Arrays;

/**
 * @program: LeetCode
 * @description: LeetCode : 322. 零钱兑换
 * @author: WXY
 * @create: 2023-01-10 12:40
 * @Version 1.0
 **/
public class Num322_coinChange {
    static int res = Integer.MAX_VALUE;

    public static int coinChange1(int[] coins, int amount) {
        if (amount == 0) return 0;
        Arrays.sort(coins);
        process1(coins, amount, coins.length - 1, 0);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    //固定参数 arr,
    //rest 目标还剩下多少，
    //index 当前来到的位置，
    //ans  当前使用了多少张硬币
    //将数组从大到小排列，每次选择最大的开始解决。，
    private static void process1(int[] coins, int amount, int index, int count) {
        if (amount == 0) {
            res = Math.min(count, res);
            return;
        }
        if (index < 0) return;
        //从最大的开始选择，每次使用i张，
        for (int i = amount / coins[index]; i >= 0 && i + count < res; i--) {
            process1(coins, amount - (i * coins[index]), index - 1, count + i);
        }
    }


    public static int coinChange2(int[] coins, int aim) {
        if (aim < 1) return 0;
        // Arrays.sort(coins);
        int[] dp = new int[aim + 1];
        return process(coins, aim, dp);
    }

    private static int process(int[] coins, int rest, int[] dp) {
        if (rest < 0) return -1;
        if (rest == 0) {
            return 0;
        }
        if (dp[rest] != 0) {
            return dp[rest];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = process(coins, rest - coin, dp);
            if (res >= 0 && res < min) {
                min = res + 1;
            }
        }
        dp[rest] = min == Integer.MAX_VALUE ? -1 : min;
        return dp[rest];
    }

    public static int coinChange4(int[] coins, int aim) {
        if (aim < 1) return 0;
        int[] dp = new int[aim + 1];
        Arrays.fill(dp,100001);
        dp[0] = 0;
        for (int i = 0; i <= aim; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }


        return dp[aim] > aim ? -1 : dp[aim];
    }


    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = 100001;
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j] && dp[i - coins[j]] != 100001) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == 100001 ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        int[] arr = {1,2,5};
        int i = coinChange(arr, 11);
        System.out.println(i);
    }
}
